package leetcode.wtx;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Given n non-negative integers a1, a2, ..., an , where each represents a point
 * at coordinate (i, ai). n vertical lines are drawn such that the two endpoints
 * of line i is at (i, ai) and (i, 0). Find two lines, which together with
 * x-axis forms a container, such that the container contains the most water.
 * 
 * Note: You may not slant the container and n is at least 2.
 * 
 * 
 * Best solution: 
 * The intuition behind this approach is that the area formed
 * between the lines will always be limited by the height of the shorter line.
 * Further, the farther the lines, the more will be the area obtained.
 * 
 * We take two pointers, one at the beginning and one at the end of the array
 * constituting the length of the lines. Futher, we maintain a variable
 * \text{maxarea}maxarea to store the maximum area obtained till now. At every
 * step, we find out the area formed between them, update \text{maxarea}maxarea
 * and move the pointer pointing to the shorter line towards the other end by
 * one step.
 * 即先从2头开始找，并记录每个步骤的max-area。下一步的走法是判断当前左右2个bar哪个低，然后
 * 在对应一侧向里走。即放弃低bar，向里走。这样可能会使得area降低，但是也可能找到更大的area。
 * 而放弃高bar向里走，则肯定会导致area降低。可以自己想想
 */
public final class Solution {
  public int maxArea(int[] height) {
    if (height == null || height.length == 1) {
      return 0;
    }
    if (height.length == 2) {
      return Math.min(height[0], height[1]);
    }
    final int NUM_HEIGHTS = height.length;
    Integer[] index = new Integer[NUM_HEIGHTS];
    for (int i = 0; i < NUM_HEIGHTS; ++i) {
      index[i] = i;
    }
    Arrays.sort(index, new Comparator<Integer>() {
      @Override
      public int compare(Integer a, Integer b) {
        return Integer.compare(height[b], height[a]);
      }
    });
    int left = index[0];
    int right = index[1];
    if (left > right) {
      left = index[1];
      right = index[0];
    }
    int maxContainer = height[index[1]] * Math.abs(index[0] - index[1]);
    for (int i = 2; i < NUM_HEIGHTS; ++i) {
      if (index[i] < left) {
        int s = (right - index[i]) * height[index[i]];
        left = index[i];
        if (s > maxContainer) {
          maxContainer = s;
        }
      } else if (index[i] > right) {
        right = index[i];
        int s = (index[i] - left) * height[index[i]];
        if (s > maxContainer) {
          maxContainer = s;
        }
      }
    }
    return maxContainer;
  }

  public int[] bruceForce(int[] height) {
    int[] ret = new int[3];
    int maxWeight = 0;
    for (int i = 0; i < height.length - 1; ++i) {
      for (int j = i + 1; j < height.length; ++j) {
        int w = Math.min(height[i], height[j]) * (j - i);
        if (w > maxWeight) {
          ret[0] = i;
          ret[1] = j;
          ret[2] = w;
          maxWeight = w;
        }
      }
    }
    return ret;
  }

  /**
   * Says hello to the world.
   * 
   * @param args
   *               The arguments of the program.
   */
  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] height = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
    System.out.println(solution.maxArea(height));
  }
}
